Bose-Chaudhuri-Hocquenghem (BCH) code is one of the most widely used error correction code (ECC) techniques in the storage and communication devices. BCH code can detect and correct random errors occurred due to channel noises and defects within memory devices. The encoding procedures of BCH codeword can be implemented by linear feedback shift register (LFSR) and some combination logics together. Comparing with encoding procedures of the BCH codewords, decoding procedures of the BCH codewords are much complicated as shown in FIG. 1. Decoding procedures are as below: After receiving a codeword (S01), in order to decode it, one should compute a syndrome according to specified polynomials (S02). Then, depending on the syndrome, an error-location polynomial can be found (S03). Next, by calculating the roots of the error-location polynomial, error-location numbers can be obtained (S04). Finally, an erroneous codeword can be corrected by above steps (S05).
A conventional linear feedback shift register circuit is shown in FIG. 2. In order to speed up operation, the circuit is often designed to be parallelization. It can calculate several inputted bit datum at the same time. The alphabet p in FIG. 2 represents the p-bit datum of the inputted R′(j) in the jth clock for synchronized calculation. After encoding, the results of Z(j) are outputted. If the code length is n bits, the procedures of encoding will complete after [n/p] clocks.
In a BCH decoder, there are some similar architectures of iterative calculation. For example, the syndrome computing unit. For a syndrome computing unit having error correcting ability t, each syndrome Si can be found by the equation below:
            S      i        =                  r        ⁡                  (                      α                          i              +              1                                )                    =                        ∑                      j            =            0                                n            -            1                          ⁢                                            r              j                        ⁡                          (                              α                                  i                  +                  1                                            )                                j                      ,          ⁢      (          i      =              1        ⁢                                  ⁢        …        ⁢                                  ⁢        t              )  r(αi+1) represents a received codeword polynomial. In order to implement the equation above, a commonly seen decoding circuit will include the syndrome computing unit for corresponding processes. A conventional syndrome computing unit is shown in FIG. 3. Similar to the aforementioned encoder, in FIG. 3, Numeral p is the number of bits received in one clock (p parallel computations). gi(j) is an intermediate data of the jth iterative operation.
The above equation can be presented in form of a matrix. Hence, common sub-expressions can be found during derivation processes. For implement of circuitry, by sharing proper hardware, the common sub-expressions can be saved. Meanwhile, the target of lowering hardware complexity can be achieved. In addition, since the encoder of the BCH code runs by using similar iterative operation, if encoding and decoding are not required to process at the same time, the encoder and syndrome computing unit can share the same registers. It further saves area cost. Many prior arts disclose such design, for example, U.S. Pat. No. 6,405,339, U.S. Pat. No. 7,743,311, U.S. Pat. No. 8,418,021, etc. However, the hardware complexities provided by those patents are still too high. For compact designed electronic devices, there is still room for improvement.